import java.util.ArrayList;

public class Deadlocks 
{
	int count = 0;
	int newDeadlocks = 0;
	private char[][] board;
	private boolean[][] boolocks;
	ArrayList<Coord> deadlocks = new ArrayList<Coord>();
	ArrayList<Coord> moreDeadlocks = new ArrayList<Coord>();
	
	public Deadlocks(){}
	
	public boolean[][] getDeadlocks( char[][] boardIn )
	{
		board = boardIn;
		boolocks = new boolean[board.length][board[0].length];
		while(true){
			count++;
	        findCornerDeadlocks();
	        findMoreDeadlocks(1);
	        findMoreDeadlocks(2);
	        findMoreDeadlocks(3);
	        findMoreDeadlocks(4);
	        addDeadlocks();
	        printDeadlocksMap();
	        printBoolocks();
	        //System.out.println("Rundor: " +count);
	        if(newDeadlocks-moreDeadlocks.size() == 0){
	        	return boolocks;
	        }
	        newDeadlocks = moreDeadlocks.size();
		}
	}
	public void printDeadlocksMap(){
		for(int i = 0; i<board[0].length; i++){
			for(int ii = 0; ii<board.length; ii++){
				System.out.print(board[ii][i]);
			}
			System.out.println();
		}
	}
	public void addDeadlocks(){
		for(int i = 0; i<deadlocks.size(); i++){
			board[deadlocks.get(i).x][deadlocks.get(i).y] = 'D';
			boolocks[deadlocks.get(i).x][deadlocks.get(i).y] = true;
		}
		for(int i = 0; i<moreDeadlocks.size(); i++){
			board[moreDeadlocks.get(i).x][moreDeadlocks.get(i).y] = 'D';
			boolocks[moreDeadlocks.get(i).x][moreDeadlocks.get(i).y] = true;
		}
	}
	public void printBoolocks(){
		System.out.println();
		System.out.println("Våran boolean array av Deadlocks:");
		int count = 0;
		for (int i = 0; i <board[0].length ; i++){
			for(int ii = 0; ii< board.length; ii++){
				if (boolocks[ii][i] == true){
					System.out.print("T");
					count++;
				}else{
					System.out.print("F");
				}
			}
			System.out.println();
		}
		System.out.println("Antal deadlocks: "+count);
		System.out.println();
	}
	public void findCornerDeadlocks(){
		for ( int x = 1; x < board.length-1; x++ )
        {
        	for ( int y = 1; y < board[0].length-1; y++ )
        	{
        		if(board[x][y] != '#' && board[x][y] != '.' && board[x][y] != '*' && board[x][y] != '+'){
        			if ( board[x+1][y] == '#' && board[x][y+1] == '#') 
        			{
        				deadlocks.add( new Coord( x, y ) );
        			}
        			if ( board[x-1][y] == '#' && board[x][y+1] == '#') 
        			{
        				deadlocks.add( new Coord( x, y ) );
        			}
        			if ( board[x-1][y] == '#' && board[x][y-1] == '#') 
        			{
        				deadlocks.add( new Coord( x, y ) );
        			}
        			if ( board[x+1][y] == '#' && board[x][y-1] == '#') 
        			{
        				deadlocks.add( new Coord( x, y ) );
        			}
        		}
        	}
        }
		addDeadlocks();
	}
	public void findMoreDeadlocks(int round){
		ArrayList<Coord> tempDeadlocks = new ArrayList<Coord>();
		for (int i = 0; i < deadlocks.size(); i++){
			Coord tempDeadlock = deadlocks.get(i);
			int ii = 1;
			boolean right = false, left = false, up = false, down = false;
			
			if(board[tempDeadlock.x+1][tempDeadlock.y] != '#'){
				right = true;
			}
			if(board[tempDeadlock.x-1][tempDeadlock.y] != '#'){
				left = true;
			}
			if(board[tempDeadlock.x][tempDeadlock.y+1] != '#'){
				down = true;
			}
			if(board[tempDeadlock.x][tempDeadlock.y-1] != '#'){
				up = true;
			}
			if(round==1){
				//Vi kan gå åt höger men inte upp.
				while(right && !up && tempDeadlock.x+ii < board.length && tempDeadlock.x+ii > 0){
					if(board[tempDeadlock.x+ii][tempDeadlock.y] == '.' || board[tempDeadlock.x+ii][tempDeadlock.y] == '+' || board[tempDeadlock.x+ii][tempDeadlock.y] == '*'){
						//right = false;
						break;
					}
					if(board[tempDeadlock.x+ii][tempDeadlock.y] == '#'){
						//right = false;
						break;
					}	
					if(board[tempDeadlock.x+ii][tempDeadlock.y-1] != '#'){
						//up = true;
						break;
					}
					if(board[tempDeadlock.x+ii][tempDeadlock.y] == 'D'){
						//right = false;
						for(int iii = 0; iii<tempDeadlocks.size(); iii++){
							if(!moreDeadlocks.contains(tempDeadlocks.get(iii))){
								moreDeadlocks.add(tempDeadlocks.get((iii)));
							}
						}
						break;
					}
					tempDeadlocks.add(new Coord(tempDeadlock.x+ii,tempDeadlock.y));
					ii++;
				}tempDeadlocks.clear();
			}
			if(round==2){
				//Vi kan gå höger men inte ner.
				while(right && !down && tempDeadlock.x+ii < board.length && tempDeadlock.x+ii > 0){
					if(board[tempDeadlock.x+ii][tempDeadlock.y] == '.' || board[tempDeadlock.x+ii][tempDeadlock.y] == '+' || board[tempDeadlock.x+ii][tempDeadlock.y] == '*'){
						//right = false;
						break;
					}
					if(board[tempDeadlock.x+ii][tempDeadlock.y] == '#'){
						//right = false;
						break;
					}	
					if(board[tempDeadlock.x+ii][tempDeadlock.y+1] != '#'){
						//down = true;
						break;
					}
					if(board[tempDeadlock.x+ii][tempDeadlock.y] == 'D' && !(board[tempDeadlock.x+ii][tempDeadlock.y] == '.')){
						//right = false;
						for(int iii = 0; iii<tempDeadlocks.size(); iii++){
							if(!deadlocks.contains(tempDeadlocks.get(iii))){
								deadlocks.add(tempDeadlocks.get((iii)));
							}
						}
						break;
					}
					tempDeadlocks.add(new Coord(tempDeadlock.x+ii,tempDeadlock.y));
					ii++;
				}tempDeadlocks.clear();
			}
			if(round==3){
				//Vi kan gå ner men inte höger.
				while(down && !right && tempDeadlock.y+ii < board[0].length && tempDeadlock.y+ii > 0 ){
					if(board[tempDeadlock.x][tempDeadlock.y+ii] == '.' || board[tempDeadlock.x][tempDeadlock.y+ii] == '+' || board[tempDeadlock.x][tempDeadlock.y+ii] == '*' ){
						//down = false;
						break;
					}
					if(board[tempDeadlock.x][tempDeadlock.y+ii] == '#'){
						//down = false;
						break;
					}	
					if(board[tempDeadlock.x+1][tempDeadlock.y+ii] != '#'){
						//right = true;
						break;
					}
					if(board[tempDeadlock.x][tempDeadlock.y+ii] == 'D' && !(board[tempDeadlock.x][tempDeadlock.y+ii] == '.')){
						//down = false;
						for(int iii = 0; iii<tempDeadlocks.size(); iii++){
							if(!moreDeadlocks.contains(tempDeadlocks.get(iii))){
								moreDeadlocks.add(tempDeadlocks.get((iii)));
							}
						}
						break;
					}
					tempDeadlocks.add(new Coord(tempDeadlock.x,tempDeadlock.y+ii));
					ii++;
				}tempDeadlocks.clear();
			}
			if(round==4){
				//Vi kan gå ner men inte vänster.
				while(down && !left && tempDeadlock.y+ii < board[0].length && tempDeadlock.y+ii > 0){
					if(board[tempDeadlock.x][tempDeadlock.y+ii] == '.' || board[tempDeadlock.x][tempDeadlock.y+ii] == '+' || board[tempDeadlock.x][tempDeadlock.y+ii] == '*' ){
						//down = false;
						break;
					}
					if(board[tempDeadlock.x][tempDeadlock.y+ii] == '#'){
						//down = false;
						break;
					}	
					if(board[tempDeadlock.x-1][tempDeadlock.y+ii] != '#'){
						//left = true;
						break;
					}
					if(board[tempDeadlock.x][tempDeadlock.y+ii] == 'D' && !(board[tempDeadlock.x][tempDeadlock.y+ii] == '.')){
						//down = false;
						for(int iii = 0; iii<tempDeadlocks.size(); iii++){
							if(!deadlocks.contains(tempDeadlocks.get(iii))){
								deadlocks.add(tempDeadlocks.get((iii)));
							}
						}
						break;
					}
					tempDeadlocks.add(new Coord(tempDeadlock.x,tempDeadlock.y+ii));
					ii++;
				}tempDeadlocks.clear();
			}
		}
	}
}
class Coord {
public int x, y;
	public Coord(int x, int y){
		this.x = x;
		this.y = y;
	}
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Coord other = (Coord) obj;
		if (x != other.x)
			return false;
		if (y != other.y)
			return false;
		return true;
	}
	public Coord clone() {
		return new Coord(x, y);
	}
	@Override
	public String toString() {
		return "Coord [x=" + x + ", y=" + y + "]";
	}
}